package com.darrenchan.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-03-30 23:01
 */
class Item {
    int i;
    int j;
    int val;

    public Item(int i, int j, int val) {
        this.i = i;
        this.j = j;
        this.val = val;
    }
}

public class QLint486 {
    public int[] mergekSortedArrays(int[][] arrays) {
        if(arrays == null || arrays.length == 0) {
            return new int[0];
        }

        Queue<Item> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        int size = 0;
        for (int i = 0; i < arrays.length; i++) {
            if(arrays[i].length > 0) {
                queue.add(new Item(i, 0, arrays[i][0]));
                size += arrays[i].length;
            }
        }

        int index = 0;
        int[] res = new int[size];
        while(!queue.isEmpty()) {
            Item poll = queue.poll();
            res[index++] = poll.val;
            if(poll.j + 1 < arrays[poll.i].length) {
                queue.add(new Item(poll.i, poll.j + 1, arrays[poll.i][poll.j + 1]));
            }
        }

        return res;
    }
}
